2. Theory
2.1 Notation Recap
| Symbol | Meaning | Dimension |
|---|
| \( m \) | Number of rows / training examples | scalar |
| \( p-1 \) | Number of raw feature columns; after adding bias column, dimension is \( p \) | scalar |
| \( x_i \) | Feature vector for example \( i \) (with \( x_{i,0} = 1 \) for the bias) | \( p \times 1 \) |
| \( y_i \) | Target / label for example \( i \) | scalar |
| \( \theta \) | Model parameter / weight vector (\( \theta_0 \) is the bias) | \( p \times 1 \) |
| \( \hat{y}_i \) | Prediction: \( \hat{y}_i = \theta^T x_i \) | scalar |
| \( \alpha \) (or \( \eta \)) | Learning rate (step-size hyperparameter) | scalar |
2.2 Gradient Descent Pseudocode (Generic)
Goal: Minimize the scalar function \( f(\theta) \).
Hyperparameters: Number of epochs \( N \), learning rate \( \eta \).
- Pick a random starting point \( p_0 \).
- For \( i = 0, \ldots, N-1 \):
- Calculate the gradient \( \nabla f(p_i) \).
- Set \( p_{i+1} = p_i - \eta \nabla f(p_i) \).
- Return \( p_N \) (the converged parameters).
2.3 Gradient Descent for Multiple Variables
For the multi-variable linear hypothesis \( h_\theta(x) = \theta_0 + \theta_1 x_1 + \cdots + \theta_{p-1} x_{p-1} = \theta^T x \)
(with \( x_0 = 1 \)) and MSE cost:
\[ J(\theta) = \frac{1}{2m} \sum_{i=1}^{m} \left( \theta^T x_i - y_i \right)^2 \]
Defining the error per example \( e_i = \theta^T x_i - y_i \), we differentiate through the chain rule:
\[ \frac{\partial J}{\partial \theta_j} = \frac{1}{2m} \sum_{i=1}^{m} 2 e_i \frac{\partial e_i}{\partial \theta_j}, \quad \frac{\partial e_i}{\partial \theta_j} = x_{i,j} \]
So the per-parameter gradient is:
\[ \frac{\partial J}{\partial \theta_j} = \frac{1}{m} \sum_{i=1}^{m} \left( \theta^T x_i - y_i \right) x_{i,j} \]
In compact matrix notation, the whole gradient vector becomes:
\[ \nabla J(\theta) = \frac{1}{m} X^T (X\theta - y) \]
And the simultaneous vectorized update:
\[ \theta := \theta - \alpha \nabla J(\theta) \]
2.4 Worked Multi-Variable GD Example
Consider the first row of a 4-column dataset (bias column \( x_0 = 1 \), then 3 real features).
Assume all four weights are initialized to \( \theta_0 = \theta_1 = \theta_2 = \theta_3 = 0.59 \),
true label \( y = 2 \), and we are processing a batch of size 1 for simplicity.
| \( x_0 \) | \( x_1 \) | \( x_2 \) | \( x_3 \) | \( \hat{y} = \theta^T x \) | \( y \) | \( e = \hat{y} - y \) | \( \partial J/\partial \theta_0 \) | \( \partial J/\partial \theta_1 \) | \( \partial J/\partial \theta_2 \) | \( \partial J/\partial \theta_3 \) |
|---|
| 1 | 1.5 | 2 | -1.2 | 1.65 | 2 | -0.35 | -0.35 · 1 | -0.35 · 1.5 | -0.35 · 2 | -0.35 · (-1.2) |
Numerical values of the gradients (click to reveal)
\begin{align}
\partial J/\partial \theta_0 &= -0.35 \\
\partial J/\partial \theta_1 &= -0.525 \\
\partial J/\partial \theta_2 &= -0.70 \\
\partial J/\partial \theta_3 &= +0.42
\end{align}
With \( \alpha = 0.1 \), the updates would increase \( \theta_0, \theta_1, \theta_2 \) and
decrease \( \theta_3 \), nudging \( \hat{y} \) upward toward the target \( y = 2 \).
2.5 The Learning Rate \( \alpha \) — Step Size of Gradient Descent
Gradient descent updates parameters by taking steps proportional to the slope of the cost
function. The step size is controlled by the hyperparameter \( \alpha \) (learning rate).
α too small
α well-tuned
α too large
- Gradient descent may be very slow
- Each step moves the parameters a tiny amount
- May require millions of epochs to converge
- Cost decreases monotonically
- Converges to the minimum in reasonable time
- Always plot J(θ) vs. epoch to confirm!
- May overshoot the minimum
- May fail to converge or even diverge entirely
- Cost J(θ) increases or oscillates with growing amplitude
2.6 Why Feature Scaling is Essential
When features have very different scales, gradient descent behaves inefficiently.
Example: House Price Prediction
- \( x_1 \): house size, range 1000 – 5000 sq ft
- \( x_2 \): bedrooms, range 1 – 5
Without scaling:
- One feature dominates gradient updates
- Cost-function contours become elongated ellipses
- GD takes a zig-zag path and converges slowly
- It becomes very hard to pick a single good learning rate for all parameters
Solution: Scale all features to comparable ranges (e.g., 0–1 min-max or standardized z-scores).
2.7 When to Stop Gradient Descent
| Strategy | How it Works |
|---|
| Cost-Change Threshold |
Stop when \( |J(t) - J(t-1)| < \varepsilon \), e.g., \( \varepsilon = 10^{-6} \) |
| Fixed Iterations |
Run for a set number of epochs, say 1000 (simplest, but may waste compute or under-converge) |
| Validation Performance |
Stop when validation error starts increasing → Early Stopping (prevents overfitting!) |
| Gradient Magnitude |
Stop when \( \|\nabla J\| < \varepsilon \) — the gradient itself is nearly zero |
2.8 Feature Selection for Regression
Feature selection improves model performance, training speed, and interpretability by
discarding irrelevant or redundant features. We focus on two regression-tailored methods.
Method 1: Correlation Filter (Model-Independent)
Earlier we saw Chi-Square, ANOVA, and other filter methods. For regression with a
continuous target, the Pearson Correlation Coefficient is the
most common filter. It measures the linear relationship between each feature and the target.
\[ r \in [-1,\ +1] \]
- \( r = +1 \): Perfect positive linear correlation
- \( r = -1 \): Perfect negative linear correlation
- \( r = 0 \): No linear correlation
- A rule of thumb: \( |r| > 0.3 \) is typically considered "meaningful"
Like other filter methods, we can either keep the top-k columns or select columns
exceeding a threshold (say \( |r| > 0.3 \)).
Note: Correlation works with one-hot encoded categorical variables, but ANOVA or Mutual Information are more statistically natural choices for purely categorical features.
Method 2: p-value-Based Selection (Embedded Method)
After training a linear regression model, we can examine the statistical significance
of each coefficient via its p-value. Formally, we test the null hypothesis:
\[ H_0: \theta_j = 0 \quad \text{("feature } j \text{ has no effect on the target")} \]
Decision rule (typical):
- p-value \( < 0.05 \) → Coefficient is statistically significant → Keep the feature
- p-value \( > 0.05 \) → Insufficient evidence that the feature matters → Consider removing
Feature Selection Families (Big Picture)
| Family | How it Works | Examples |
|---|
| Filter |
Select features before training, using statistical tests independent of the final model |
Chi-square, ANOVA, Pearson Correlation, Mutual Information |
| Wrapper |
Train the model many times with different subsets to pick the best-performing subset |
Forward Selection, Backward Elimination, Recursive Feature Elimination (RFE) |
| Embedded |
Feature selection happens during / as a byproduct of model training |
Tree-based feature importances, Lasso (Unit 18!), p-value pruning |
4. Numerical Solutions
Problem 1: Vectorized Gradient on Small Matrix
Mini-batch of 3 examples, 2 real features + bias column (p = 3):
\[
X = \begin{bmatrix} 1 & 1 & 2 \\ 1 & 3 & 4 \\ 1 & 5 & 6 \end{bmatrix},\quad
y = \begin{bmatrix} 2 \\ 7 \\ 10 \end{bmatrix},\quad
\theta = \begin{bmatrix} 0 \\ 1 \\ 1 \end{bmatrix}
\]
📘 Compute \( \nabla J(\theta) \) step-by-step
Step 1: Predictions \( \hat{y} = X\theta \):
\[ \hat{y} = \begin{bmatrix} 0+1+2 \\ 0+3+4 \\ 0+5+6 \end{bmatrix} = \begin{bmatrix} 3 \\ 7 \\ 11 \end{bmatrix} \]
Step 2: Residual \( \hat{y} - y \):
\[ \hat{y} - y = \begin{bmatrix} 3-2 \\ 7-7 \\ 11-10 \end{bmatrix} = \begin{bmatrix} +1 \\ 0 \\ +1 \end{bmatrix} \]
Step 3: \( X^T (\hat{y} - y) \) (pre-factor):
\[
X^T (\hat{y}-y) =
\begin{bmatrix} 1 & 1 & 1 \\ 1 & 3 & 5 \\ 2 & 4 & 6 \end{bmatrix}
\begin{bmatrix} 1 \\ 0 \\ 1 \end{bmatrix}
= \begin{bmatrix} 1+0+1 \\ 1+0+5 \\ 2+0+6 \end{bmatrix}
= \begin{bmatrix} 2 \\ 6 \\ 8 \end{bmatrix}
\]
Step 4: Divide by \( m = 3 \):
\[ \nabla J(\theta) = \frac{1}{3} \begin{bmatrix} 2 \\ 6 \\ 8 \end{bmatrix} = \begin{bmatrix} \mathbf{2/3} \\ \mathbf{2} \\ \mathbf{8/3} \end{bmatrix} \]
Problem 2: Feature Scaling Effect
Two features predicting house price: size in sq ft (\( x_1 \in [500, 5000] \))
and bedrooms (\( x_2 \in [1, 5] \)). A GD step updates:
\( \theta_1 := \theta_1 - \alpha \cdot 4000 \), \( \theta_2 := \theta_2 - \alpha \cdot 0.1 \).
📘 Diagnose + Fix (Standardization)
Diagnosis: The gradient for \( \theta_1 \) is 40,000× larger than for \( \theta_2 \),
so \( \theta_1 \) moves drastically while \( \theta_2 \) creeps. A single α cannot serve both well.
Fix — Standardize both features:
\[ z = \frac{x - \mu}{\sigma} \]
After standardization, \( \mu = 0 \) and \( \sigma = 1 \) for both features. Now both gradients are on the same scale and a single well-chosen α works for all parameters.
Problem 3: Correlation + p-value Combined Reasoning
Feature A: Pearson r = +0.02 with target, p-value = 0.01 after regression.
Feature B: Pearson r = +0.55 with target, p-value = 0.20 after regression.
📘 Step-by-Step Interpretation
Step 1: Feature A (r = 0.02, p = 0.01)
- Marginal correlation with target is tiny → a correlation filter would drop it.
- But in the multi-variate model, its coefficient is statistically significant (p < 0.05).
- Interpretation: A has little univariate linear relation but helps prediction conditional on the other features (suppression / interaction effect). Keep A.
Step 2: Feature B (r = 0.55, p = 0.20)
- Univariate correlation is strong → a correlation filter would keep it.
- But in the full model, its coefficient is not statistically significant.
- Likely cause: B is highly correlated with another feature already in the model (multicollinearity). The model doesn't "need" both. Consider removing B or the collinear partner (use cross-validated performance to decide).
Takeaway: Correlation and p-values answer different questions. Use both, not either one in isolation.